package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-23 09:33
 * @description: Functions of this class is 找出旋转数组中的最小元素
 * 官方题解（二分查找）：
 * class Solution {
 *     public int minArray(int[] numbers) {
 *         int left=0;
 *         int right=numbers.length-1;
 *         while(left<right){
 *             int mid=left+(right-left)/2;
 *             if(numbers[mid]<numbers[right]){
 *                 right=mid;
 *             }
 *             else if(numbers[mid]>numbers[right]){
 *                 left=mid+1;
 *             }
 *             else{
 *                 right--;
 *             }
 *         }
 *         return numbers[left];
 *     }
 * }
 **/
public class NoNo旋转数组中的最小元素 {
    public static void main(String args[]){
        int nums[]={5,6,1,2,3,4};
        System.out.println("最小元素为："+getMin(nums));
        int nums1[]={1,1,1,1,1,2};
        System.out.println("最小元素为："+getMin(nums1));
        int nums3[]={1,2,3,4,5};
        reverseNums(nums3,2);
        System.out.println(Arrays.toString(nums3));
        System.out.println("最小元素为："+getMin(nums3));

    }
    private static int getMin(int nums[],int left,int right){
        //如果旋转个数为0，即没有旋转，即直接返回头部元素
        if(right<left){
            return nums[0];
        }
        if(left==right){
            return nums[left];
        }
        int mid=(left+(right-left))>>1;
        //开始判断中间的值是否是最小值
        if (mid == 0 || nums[mid] < nums[mid - 1]) {
            //说明切分已经到头了 或者中间元素小于其上一个元素
            return nums[mid];
        } else if (nums[mid + 1] < nums[mid]) {
            return nums[mid + 1];
        } else if (nums[right] > nums[mid]) {
            //如果最左边的元素大于中间值，则说明最小元素一定在左半部分
            return getMin(nums, left, mid - 1);
        } else if (nums[left] < nums[mid]) {
            //如：1 1 2 1 1 1 说明最小元素一定在右半部分
            return getMin(nums, mid + 1, right);
        } else {
            //说明既有可能在左边，也有可能在右边
            return Math.min(getMin(nums, left, mid-1),getMin(nums,mid+1,right));
        }
    }
    private static int getMin(int nums[]){
        if(nums==null){
            return -1;
        }
        return getMin(nums,0,nums.length-1);
    }
    private static void reverseNums(int nums[],int index){
        if(nums==null||index<0||index>nums.length||index==nums.length-1){
            return;
        }
        swap(nums,0,index);
        swap(nums,index+1,nums.length-1);
        swap(nums,0,nums.length-1 );
    }
    private static void swap(int nums[],int left,int right){
        //进行元素的交换
        for(;left<right;left++,right--){
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
        }
    }
}